package tulingxueyuan117;

import java.util.HashSet;

/**
 * Author: Zhang Dongwei
 * Date: 2022/5/22 19:13
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 * 不允许修改 链表。
 * /**
 *  * Definition for singly-linked list.
 *  * class ListNode {
 *  *     int val;
 *  *     ListNode next;
 *  *     ListNode(int x) {
 *  *         val = x;
 *  *         next = null;
 *  *     }
 *  * }
 */
public class p14_环形链表II_142 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode1;

        ListNode res = detectCycle(listNode);
        System.out.println(res);

    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

//    视频讲解
//    public static ListNode detectCycle(ListNode head) {
//        if(head == null) return null;
//        ListNode slowPtr = head;
//        ListNode fastPtr = head;
//        boolean loopExists = false;
//        while (fastPtr.next != null && fastPtr.next.next != null){
//            slowPtr = slowPtr.next;
//            fastPtr = fastPtr.next.next;
//            if(slowPtr == fastPtr){
//                loopExists = true;
//                break;
//            }
//        }
//        if(loopExists){ // 环存在
//            slowPtr = head;
//            while (slowPtr != fastPtr){
//                fastPtr = fastPtr.next;
//                slowPtr = slowPtr.next;
//            }
//            return slowPtr; // 返回环的开始结点
//        }
//        return null; // 环不存在
//    }

//    哈希表
    public static ListNode detectCycle(ListNode head){
        ListNode pos = head;
        HashSet<ListNode> listNodes = new HashSet<>();
        while (pos != null){
            if(listNodes.contains(pos)){
                return pos;
            }else {
                listNodes.add(pos);
                pos = pos.next;
            }
        }
        return null;
    }
}
